W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Jaskinia Bajtocka składa się z komór oraz z łączących je korytarzy. Nie wychodząc z jaskini, pomiędzy każdą parą komór można przejść bez zawracania na dokładnie jeden sposób. W niektórych komorach pozostawiono dynamit. Wzdłuż każdego korytarza rozciągnięto lont. W każdej komorze wszystkie lonty z prowadzących do niej korytarzy są połączone, a jeżeli w danej komorze znajduje się dynamit, to jest on połączony z lontem. Lont biegnący korytarzem pomiędzy sąsiednimi komorami spala się w jednej jednostce czasu, a dynamit wybucha dokładnie w chwili, gdy ogień znajdzie się w komorze zawierającej ten dynamit.
Chcielibyśmy równocześnie podpalić lonty w jakichś komorach (w miejscu połączenia lontów) w taki sposób, aby wszystkie ładunki dynamitu wybuchły w jak najkrótszym czasie, licząc od momentu podpalenia lontów. Napisz program, który wyznaczy najkrótszy możliwy taki czas.
Pierwszy wiersz standardowego wejścia zawiera dwie liczby całkowite i (), oddzielone pojedynczym odstępem i oznaczające odpowiednio liczbę komór w jaskini oraz liczbę komór, w których możemy podpalić lonty. Komory są ponumerowane od 1 do . Kolejny wiersz zawiera liczb całkowitych (), pooddzielanych pojedynczymi odstępami. Jeśli , to w -tej komorze znajduje się dynamit, a jeśli , to nie ma w niej dynamitu. Kolejne wierszy opisuje korytarze w jaskini. W każdym z nich znajdują się dwie liczby całkowite () oddzielone pojedynczym odstępem i oznaczające, że istnieje korytarz łączący komory i . Każdy korytarz pojawia się w opisie dokładnie raz.
Możesz założyć, że w testach wartych łącznie 10\% punktów zachodzi dodatkowy warunek , a w testach wartych łącznie 40\% punktów zachodzi .
Pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać jedną liczbę całkowitą, równą minimalnemu czasowi od podpalenia lontów, po jakim wybuchną wszystkie ładunki dynamitu.
Dla danych wejściowych:
7 2 1 0 1 1 0 1 1 1 3 2 3 3 4 4 5 5 6 5 7
poprawną odpowiedzią jest:
1
Wyjaśnienie do przykładu: Podpalamy lonty w komorach 3 i 5. W chwili zero wybucha dynamit w komorze 3, a po jednostce czasu zapalone zostają dynamity w komorach 1, 4, 6 i 7.
Autor zadania: Jacek Tomasiewicz.